// @test([4,2,5,1,3])=[1,2,3,4,5]
// @algorithm @lc id=100305 lang=javascript
// @title er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function (root) {
  // 树为空，链表也是空
  if (root === null) return null;
  // 中序遍历
  const inorder = (node) => {
    if (node === null) return;
    inorder(node.left);
    // 双向链表
    node.left = p;
    p.right = node;
    p = p.right;
    inorder(node.right);
  };
  // 虚拟头节点
  const head = new Node(null, null, null);
  // 当前头指针
  let p = head;
  inorder(root);
  // 头尾相连，循环链表
  head.right.left = p;
  p.right = head.right;
  return head.right;
};
